package com.company;

/**
 * @author zhf
 * @date 2021/11/25
 */

import java.util.*;

/**
 * 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
 */
public class MaxRec {
    public static void main(String[] args) {
//        char[][] matrix = new char[][]{{'1','0','0','1','0'},{'1','0','1','0','0'},{'1','1','1','1','0'},{'1','1','0','1','0'}};
//        char[][] matrix = new char[][]{{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
//        char[][] matrix = new char[][]{{'0'}};
//        char[][] matrix = new char[][]{{'1'}};
//        char[][] matrix = new char[][]{{}};
        char[][] matrix = new char[][]{{'1','0'},{'0','1'}};

        MaxRec maxRec = new MaxRec();
        int ans = maxRec.maximalRectangle(matrix);
        System.out.println(ans);
    }

    /*
    单调栈，先将行求柱形面积，然后计算列的
     */
    public int maximalRectangle(char[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int[] list = new int[n];
        int maxnum = 0;
        if (n == 0) {
            return 0;
        }
        for (int i = 0; i <= n - 1; i++) {
            int num = 0;
            for (int j = 0; j <= m - 1; j++) {
                if (matrix[i][j] == '0') {
                    num = 0;
                }
                if (matrix[i][j] == '1'){
                    num = num + 1;
                }
                maxnum = Math.max(maxnum,num);
            }
            list[i] = maxnum;
            maxnum = 0;
        }
        int ans = largestRectangleArea(list);
        System.out.println(Arrays.toString(list));;
        return ans;
    }
    public int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int len = heights.length;
        int[] left = new int[len];
        int[] right = new int[len];
        int Maxarea = 0;
        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
                stack.pop();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        stack.clear();
        for (int i = len - 1; i >= 0; i--) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
                stack.pop();
            }
            right[i] = stack.isEmpty() ? len : stack.peek();
            stack.push(i);
        }
        for (int i = 0; i < len; i++) {
            Maxarea = Math.max(Maxarea,heights[i] * (right[i] - left[i] - 1));
        }
        return Maxarea;
    }
}
